In my last post Tree Data Structures I discussed modelling a tree as a raw data structure. That is, a self-describing tree node. In this post I offer some terminology and search/traversal techniques.
Top
In this post...
TopWhat Is A Tree?
The following diagram illustrates a basic tree structure.
A tree is data structure that consists of nodes. A tree typically contains a root node (though may contain multiple root nodes). Each tree node contains data that may be searched/traversed.
TopExamples Of Tree Usage
Trees are an important data structure, examples of use now follow...
Abstract Syntax Tree (AST)
Parsing is essentally data transformation. Take a sequence of characters and produce tokens. One or more tokens are then transformed to create abstract syntax tree nodes (Expressions, Assignment and so on). These nodes can be run against a runtime engine to run script type code. Most modern computer languages follow this idea. AST's can further be transformed to generate intermediate language code (aka byte code).
A Document Object Model
HTML uses a tree structure to describe page elements. The DOM may be manipulated, once the HTML document is fully loaded. The DOM allows new HTML insertion, modifying existing elements and so on. This gives rise to the so-called "dynamic content".
Hierarchical Data
This is possibly where trees excel. Most data is hierarchical in nature. Consider the following simple examples.
- A company
Has a CEO. The CEO might manage numerous managers. Managers, manage workers. - A Family
Has a head of the family. Has grandparents. Has offspring which in turn will have their own offspring.
Tree Terminology
Assuming the following tree...
- A is the root node.
- Node B1, B2, B3 are child nodes of the root node, A
Examples
childrenOf(A) => B1, B2, B3
childrenOf(B3) => c1, c2
- Node A, the root node, is also the parent node of nodes B1, B2, B3
Examples
parent(B1) => A
parent(B2) => A
- Nodes without child nodes are known as leaf nodes.
Nodes B1, B2, C1 and D1 in the diagram are leaf nodes as they have no child nodes. - Nodes have a depth or level.
The root node(s) are always level 1.
Node D1, has the highest depth level of 4.
Examples
depth(A) => 1
depth(B1) => 2
depth(D1) => 4
- All nodes bar the root node A are descendants of the root node.
Examples
descendants(A) => B1, B2, B3, C1, C2, D1 descendants(B3) => C1, C2, D1 - Sibling nodes are nodes that exist on the same level of the node in question.
Examples
siblings(A) => none
siblings(B1) => B2, B3
siblings(C1) => C2
No comments:
Post a Comment